import java.util.Arrays;

/**
 * 976. 三角形的最大周长
 * https://leetcode-cn.com/problems/largest-perimeter-triangle/
 */
public class Solutions_976 {
    public static void main(String[] args) {
//        int[] nums = {2, 1, 2};  // output: 5
//        int[] nums = {1, 2, 1};  // output: 0
//        int[] nums = {3, 2, 3, 4};  // output: 10
        int[] nums = {3, 6, 2, 3};  // output: 8

        int result = largestPerimeter(nums);
        System.out.println(result);
    }

    /**
     * 思路：对数组 A 进行排序，利用三角形特征，贪心思想完成
     * 排序后，如果最大的一条边没有小于前面两条边的和，那么就不能选择这条最大的边
     */
    public static int largestPerimeter(int[] A) {
        Arrays.sort(A);
        // 三条边组成三角形的充分必要条件：任意两边之和大于第三边
        // 即：较小的两条边之和大于最大的边
        // 最大周长：三边之和最大
        for (int i = A.length - 1; i >= 2; i--) {
            if (A[i - 1] + A[i - 2] > A[i]) {
                return A[i - 2] + A[i - 1] + A[i];
            }
        }
        return 0;
    }
}
